import random


def insert_sort_gap(li: list, gap: int):
    n = len(li)
    for i in range(gap, n):  # i 表示拿到的元素的下标
        tmp = li[i]
        j = i - gap  # 有序区要对比的元素
        while j >= 0 and li[j] > tmp:  # 如果摸到的元素比有序区的元素小，并且有序区有元素
            li[j + gap] = li[j]
            j -= gap
        li[j + gap] = tmp
    return li


def shell_sort(li: list):
    d = len(li) // 2
    while d >= 1:
        insert_sort_gap(li, d)
        d //= 2
    return li


li = [random.randint(1, 100) for i in range(20)]
print(li)
li = shell_sort(li)
print(li)
